package Algorithm.backTracking.practice;

import java.util.ArrayList;
import java.util.List;

/**
 * 17. 电话号码的字母组合 https://leetcode.cn/problems/letter-combinations-of-a-phone-number
 */
public class LetterCombinations {

    public static void main(String[] args) {
        new LetterCombinations().letterCombinations("23");
    }

    /**
     * 思路：回溯算法
     */
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if(digits.length() > 0) {
            backTracing(result, new StringBuilder(), digits, 0);
        }
        return result;
    }

    public void backTracing(List<String> result, StringBuilder path, String digits, int nextPathIndex) {
        if(nextPathIndex == digits.length()) {
            result.add(path.toString());
            return;
        }
        int number = digits.charAt(nextPathIndex) - '0';
        int begin,end;//下一步路径选择列表起始字符和终止字符的Unicode编码值
        if(number <= 6) {
            begin = 'a' + (number-2)*3;
            end = begin + 2;
        } else if(number == 7) {
            begin = 'p';
            end = begin + 3;
        } else if(number == 8) {
            begin = 't';
            end = begin + 2;
        } else {
            begin = 'w';
            end = begin + 3;
        }
        for(int i=begin;i <= end;i++) {
            path.append((char)i);
            //用nextPathIndex+1而非nextPathIndex++
            backTracing(result, path, digits, nextPathIndex+1);
            path.deleteCharAt(path.length()-1);
        }
    }

}
